#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void CountingSort(int* arr, int rangeL, int rangeR, int N)
{
    int nCounting = rangeR - rangeL + 1;
    int* counting = (int*)malloc(nCounting * sizeof(int));
    memset(arr, 0, nCounting * sizeof(int));
    for(int i = 0; i < N; i++)
    {
        counting[arr[i] - rangeL]++;
    }
    for(int i = 0, j = 0; i < nCounting; i++)
    {
        for(; counting[i]; j++, counting[i]--)
        arr[j] = i + rangeL;
    }
    free(counting);
}

void isSort(int* arr, int N)
{
    for(int i = 0; i < N - 1; i++)
    {
        if(arr[i] > arr[i + 1])
        {
            printf("Not sorted.\n");
            return;
        }
    }
    printf("Sorted.\n");
}

void print(int* arr, int N)
{
    for(int i = 0; i < N; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main()
{
    srand(time(NULL));
    int N = 1000;
    int range = 101;
    int* arr = (int*)malloc(N * sizeof(int));
    for(int i = 0; i < N; i++)
    {
        arr[i] = rand() % range;
    }
    
   //int arr[10] = { 1, 2, 7, 6, 9, 0, 4, 8, 5, 3};
   //int N = 10;

    
    CountingSort(arr, 0, range - 1, N);
    print(arr, N);
    isSort(arr, N);

    return 0;
}
